import java.util.HashMap;
import java.util.Map;

public class Leetcode1138 {

    private static final Map<Character, int[]> KEY_INDEX_MAP = new HashMap<>();

    static {
        KEY_INDEX_MAP.put('a', new int[]{0, 0});
        KEY_INDEX_MAP.put('b', new int[]{0, 1});
        KEY_INDEX_MAP.put('c', new int[]{0, 2});
        KEY_INDEX_MAP.put('d', new int[]{0, 3});
        KEY_INDEX_MAP.put('e', new int[]{0, 4});
        KEY_INDEX_MAP.put('f', new int[]{1, 0});
        KEY_INDEX_MAP.put('g', new int[]{1, 1});
        KEY_INDEX_MAP.put('h', new int[]{1, 2});
        KEY_INDEX_MAP.put('i', new int[]{1, 3});
        KEY_INDEX_MAP.put('j', new int[]{1, 4});
        KEY_INDEX_MAP.put('k', new int[]{2, 0});
        KEY_INDEX_MAP.put('l', new int[]{2, 1});
        KEY_INDEX_MAP.put('m', new int[]{2, 2});
        KEY_INDEX_MAP.put('n', new int[]{2, 3});
        KEY_INDEX_MAP.put('o', new int[]{2, 4});
        KEY_INDEX_MAP.put('p', new int[]{3, 0});
        KEY_INDEX_MAP.put('q', new int[]{3, 1});
        KEY_INDEX_MAP.put('r', new int[]{3, 2});
        KEY_INDEX_MAP.put('s', new int[]{3, 3});
        KEY_INDEX_MAP.put('t', new int[]{3, 4});
        KEY_INDEX_MAP.put('u', new int[]{4, 0});
        KEY_INDEX_MAP.put('v', new int[]{4, 1});
        KEY_INDEX_MAP.put('w', new int[]{4, 2});
        KEY_INDEX_MAP.put('x', new int[]{4, 3});
        KEY_INDEX_MAP.put('y', new int[]{4, 4});
        KEY_INDEX_MAP.put('z', new int[]{5, 0});
    }

    public static String alphabetBoardPath(String target) {
        char[] targetChars = target.toCharArray();

        StringBuilder res = new StringBuilder();

        int parentX = 0;
        int parentY = 0;
        for (char targetChar : targetChars) {
            int[] index = KEY_INDEX_MAP.get(targetChar);
            int diffX = index[0] - parentX;
            int diffY = index[1] - parentY;
            //去z家先左右
            if (targetChar == 'z') {
                res.append((diffY > 0 ? "R" : "L").repeat(Math.abs(diffY)));
                res.append((diffX > 0 ? "D" : "U").repeat(Math.abs(diffX)));
            //z出门先上下
            } else if (parentX == 5 && parentY == 0) {
                res.append((diffX > 0 ? "D" : "U").repeat(Math.abs(diffX)));
                res.append((diffY > 0 ? "R" : "L").repeat(Math.abs(diffY)));
            //其他家出门随意
            }else{
                res.append((diffY > 0 ? "R" : "L").repeat(Math.abs(diffY)));
                res.append((diffX > 0 ? "D" : "U").repeat(Math.abs(diffX)));
            }


            res.append("!");
            parentX = index[0];
            parentY = index[1];
        }
        return res.toString();
    }

    public static void main(String[] args) {
        System.out.println(alphabetBoardPath("zdz"));
    }
}

